package 基础;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/*
1.hash
•hash是一种函数，一般翻译为散列，是把任意长度的输入通过散列算法变换成固定长度的输出，该输出就是hashcode（散列值/哈希码）；
•这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值；
•简单地说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
常用hash函数：直接取余法、乘法取整法、平方取中法等。

2. hashcode
把任意长度的输入通过hash算法变换成固定长度的输出，该输出就是hashcode。

3. hashcode的作用
hashcode的存在主要是为了查找的快捷性。

比如：我们要存放1000个不一样的数字，用最笨的方法，就是存一个数字，就遍历一遍，看有没有相同的数，当存了100个数字，开始存第101个数的时候，就需要跟100个数字进
行比较，这样就很消耗时间。

如果用hashcode来记录对象的位置，假设hash表中有1、2、3、4、5、6、7、8个位置，存第一个数，hashcode为1，该数就放在hash表中1的位置，存到100个数字，hash表
中8个位置会有很多数字了，1中可能有20个数字，存第101个数时，先得到该数的hashcode，假设为1，那么就有20个数字和它的hashcode相同，它只需要跟这20个数字相
比较(equals())，这样比较的次数就少了很多，提高了效率。

4. equals()和hashcode的关系
•先通过hashcode比较，如果hascode相等，就用equals()来比较两个对象的内容是否相等；
•如果两个对象equals()为true，那么这两个对象的hashcode一定相等；
•如果两个对象的hashcode相等，不代表两个对象equals()为true，只能说明这两个对象在散列存储结构中，存放于同一个位置。

5. 为什么equals()重写的话，建议也一起重写hashcode方法？
首先要保证一个原则，两对象如果equlas出来的结果相等，那么hashCode也一定相等。

如果有一个类重写了equals方法，但没有重写hashcode方法，那么当类的两个对象使用equals()比较时相等，但两者的hashcode不一样相等，这就导致了错误。

例如：

User u1 = new User(“张三”);
User u2 = new User(“张三”);

如果User类重写了equals()方法，使得 u1.equals(u2)返回true ；但是User类没有重写hashCode方法，它用的是Object类的hashCode方法，所
以 u1.hashCode = 31050006 u2.hashCode = 31587890，两者的hashCode并不相等。



一，哈希算法的概念

    在计算机领域，哈希算法具有非常广泛的应用，比如快速查找和加密。今天我们来讨论一下哈希算法。我们先从理论知识开始。

1，什么是哈希算法
    百科中，从哈希算法的功能上，对哈希算法进行了定义。百科是这样定义哈希算法的：哈希算法可以将任意长度的二进制值映射
为较短的，固定长度的二进制值。我们把这个二进制值成为哈希值。

2，哈希值的特点
  • 哈希值是二进制值；
  • 哈希值具有一定的唯一性；
  • 哈希值极其紧凑；
  • 要找到生成同一个哈希值的2个不同输入，在一定时间范围内，是不可能的。

   正因为哈希值的这些特点，使得哈希算法应用在加密领域成为可能。哈希算法在加密领域的应用，源于哈希算法的不可逆性，对于用户输入的密码，通过哈希算法可以
得到一个哈希值。并且，同一个密码，生成的哈希值总是相等的。这样，服务器就可以在不知道用户输入的密码的情况下，判断用户输入的密码是否正确。

3，哈希表
   哈希表是一种数据机构。哈希表根据关键字（key），生成关键字的哈希值，然后通过哈希值映射关键字对应的值。哈希表存储了多余的key（我们本可以只存储值的），
是一种用空间换时间的做法。在内存足够的情况下，这种“空间换时间”的做法是值得的。哈希表的产生，灵感来源于数组。我们知道，数组号称查询效率最高的数据结构，
因为不管数组的容量多大，查询的时间复杂度都是O(1)。如果所有的key都是不重复的整数，那么这就完美了，不需要新增一张哈希表，来做关键字（key）到值（value）的
映射。但是，如果key是字符串，情况就不一样了。我们必须要来建一张哈希表，进行映射。
   数据库索引的原理，其实和哈希表是相同的。数据库索引也是用空间换时间的做法。

二，哈希算法的具体实现
   哈希算法在不同的语言，具有不同的实现。这里我们以java语言为例来进行说明。

1，哈希算法在HashMap类中的应用
   java中的集合，比如HashMap/Hashtable/HashSet等，在实现时，都用到了哈希算法。当我们向容器中添加元素时，我们有必要知道这个元素是否已经存在。
   从实现上来说，java是借助hashcode()方法和equals()方法来实现判断元素是否已经存在的。当我们向HashMap中插入元素A时，首先，调用hashcode()方法，判
断元素A在容器中是否已经存在。如果A元素的hashcode值在HashMap中不存在，则直接插入。否则，接着调用equals()方法，判断A元素在容器中是否已经存在。hashcode()
的时间复杂度为O(1)，equals()方法的时间复杂度为O(m)，整体的时间复杂度就是：O(1) + O(m)。其中，m是桶的深度。桶的深度是一个什么概念呢，桶的深度是指具有
相同hashcode值得元素的个数，也就是发生哈希碰撞的元素的个数。
    一个好的哈希算法应该尽量减少哈希碰撞的次数。

2，哈希算法在String类中的应用
   Sring类重写了Object类的equals()方法和hashcode()方法。hashcode()方法的源代码如下：

public int hashCode() {
	int h = hash;// Default to 0
	if (h == 0) {
    	int off = offset;
    	char val[] = value;
    	int len = count;
 
      for (int i = 0; i < len; i++) {
          h = 31*h + val[off++];
      }
      hash = h;
   }
   return h;
}

    源代码写的比较简洁，阅读起来也不是太方便，下面我详细解读一下：
// String类的hashcode值（哈希值）是如何计算得到的？具体实现？为了方便阅读，我们来进行分步说明
static void hashcodeTest(){
	
	String str = "yangcq";
	
	// 第一步 = (int)'y'
	// 第二步 = (31 * (int)'y') + (int)'a'
	// 第三步 = 31 * ((31 * (int)'y') + (int)'a') + (int)'n'
	// 第四步 = 31 * (31 * ((31 * (int)'y') + (int)'a') + (int)'n') + (int)'g'
	// 第五步 = 31 * (31 * (31 * ((31 * (int)'y') + (int)'a') + (int)'n') + (int)'g') + (int)'c'
	// 第六步 = 31 * (31 * (31 * (31 * ((31 * (int)'y') + (int)'a') + (int)'n') + (int)'g') + (int)'c') + (int)'q'
	
	// 上面的过程，也可以用下面的方式表示
	
	// 第一步 = (int)'y'
	// 第二步 = 31 * (第一步的计算结果) + (int)'a'
	// 第三步 = 31 * (第二步的计算结果) + (int)'n'
	// 第四步 = 31 * (第三步的计算结果) + (int)'g'
	// 第五步 = 31 * (第四步的计算结果) + (int)'c'
	// 第六步 = 31 * (第五步的计算结果) + (int)'q'
	
	int hashcode = 31 * (31 * (31 * (31 * ((31 * (int)'y') + (int)'a') + (int)'n') + (int)'g') + (int)'c') + (int)'q';
	System.out.println("yangcq的hashcode = " + hashcode);        // yangcq的hashcode = -737879313
	System.out.println("yangcq的hashcode = " + str.hashCode());  // yangcq的hashcode = -737879313
	
}

   通过上面的测试方法，我们可以很清晰的看到hashcode()方法具体的计算过程。下面再贴上2个类，一个是自己写的测试类MyHashcode.java，另一个是HashcodeOfString.java

java中对象的hashcode值，是如何计算得到的。*/
/*
//public class MyHashcode {
public class hash与hashcode {	
   static char value[]; // The value is used for character storage.
   static int offset;//The offset is the first index of the storage that is used.
   static int count;//The count is the number of characters in the String.
   static int hash; //Cache the hash code for the string   Default to 0    
	public static void main(String[] args) {
		String str1 = new String("yangcq");
		String str2 = new String("yangcq");
		// 如果2个字符串的内容相同，那么这2个字符串的hashcode必然相同
		System.out.println(new String("yangcq").hashCode() == new String("yangcq").hashCode());
		System.out.println(str1.hashCode() == str2.hashCode());
		
		System.out.println(str1.hashCode());
		System.out.println(hashCode1(str1));
		
		// 测试自定义的hashcode方法
		HashcodeOfString hashcodeOfString = new HashcodeOfString();
		hashcodeOfString.hashCode(str1);
		System.out.println("str1的hashcode = " + hashcodeOfString.hashCode(str1));
		System.out.println("str1的hashcode = " + str1.hashCode());
	}
	
	// HashMap中实现的hash算法(再hash算法)
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);//h=h^(h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    
    // String类实现的hashcode方法源代码
    static int hashCode1(String str) {
		int h = hash;
		if (h == 0) {
			int off = 0;
			char val[] = str.toCharArray();
			int len = str.length();
 
			for (int i = 0; i < len; i++) {
				h = 31 * h + val[off++];
			}
			hash = h;
		}
		return h;
	}
    
    // String类的hashcode值（哈希值）是如何计算得到的？具体实现？为了方便阅读，我们来进行分步说明
    static void hashcodeTest(){
    	
    	String str = "yangcq";
    	
    	// 第一步 = (int)'y'
    	// 第二步 = (31 * (int)'y') + (int)'a'
    	// 第三步 = 31 * ((31 * (int)'y') + (int)'a') + (int)'n'
    	// 第四步 = 31 * (31 * ((31 * (int)'y') + (int)'a') + (int)'n') + (int)'g'
    	// 第五步 = 31 * (31 * (31 * ((31 * (int)'y') + (int)'a') + (int)'n') + (int)'g') + (int)'c'
    	// 第六步 = 31 * (31 * (31 * (31 * ((31 * (int)'y') + (int)'a') + (int)'n') + (int)'g') + (int)'c') + (int)'q'
    	
    	// 上面的过程，也可以用下面的方式表示
    	
    	// 第一步 = (int)'y'
    	// 第二步 = 31 * (第一步的计算结果) + (int)'a'
    	// 第三步 = 31 * (第二步的计算结果) + (int)'n'
    	// 第四步 = 31 * (第三步的计算结果) + (int)'g'
    	// 第五步 = 31 * (第四步的计算结果) + (int)'c'
    	// 第六步 = 31 * (第五步的计算结果) + (int)'q'
    	
    	int hashcode = 31 * (31 * (31 * (31 * ((31 * (int)'y') + (int)'a') + (int)'n') + (int)'g') + (int)'c') + (int)'q';
    	System.out.println("yangcq的hashcode = " + hashcode);        // yangcq的hashcode = -737879313
    	System.out.println("yangcq的hashcode = " + str.hashCode());  // yangcq的hashcode = -737879313
    	
    }
}


 //@yangcq
 //@描述：String类的hashcode值是如何计算得到的。
 //参考String类的hashcode()方法，写一个方法，计算任意字符串的hashcode
 
 //哈希值的特点：
 // 1，一定程度的唯一性；
 // 2，长度固定；
 // 3，哈希值是二进制值；
 // 4，要找到生成相同哈希值的2个不同输入，在有限时间内是不可能的；哈希算法应用于加密领域的原因。

class HashcodeOfString implements java.io.Serializable{
 
	private static final long serialVersionUID = -4208161728160233397L;
	
    public int hashCode(String str) {
    	// 最终计算得出的哈希值，转化为int以后的哈希值
    	int hashcode = 0;
    	// 临时哈希值变量
    	int hash = 0;
		if (hash == 0) {
			// 当前char的索引
			int off = 0;
			// 字符串str的字符数组表示
			char val[] = str.toCharArray();
			// 字符串str的长度
			int len = str.length();
			for (int i = 0; i < len; i++) {
				hash = 31 * hash + val[off++];
			}
			hashcode = hash;
		}
		return hashcode;
	}
}
*/
/*
1. 二进制计算的一些基础知识

<<  : 左移运算符，num << 1,相当于num乘以2  低位补0
>>  : 右移运算符，num >> 1,相当于num除以2  高位补0
>>> : 无符号右移，忽略符号位，空位都以0补齐
 %  : 模运算 取余
 ^  :   位异或 第一个操作数的的第n位于第二个操作数的第n位相反，那么结果的第n为也为1，否则为0
 &  : 与运算 第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0
 |  :  或运算 第一个操作数的的第n位于第二个操作数的第n位 只要有一个是1，那么结果的第n为也为1，否则为0
 ~  : 非运算 操作数的第n位为1，那么结果的第n位为0，反之，也就是取反运算（一元操作符：只操作一个数）

2. 为什么使用 hashcode
那么我们就说说为什么使用 hashcode ，hashCode 存在的第一重要的原因就是在 HashMap(HashSet 其实就是HashMap) 中使用（其实Object 类
的 hashCode 方法注释已经说明了 ），我知道，HashMap 之所以速度快，因为他使用的是散列表，根据 key 的 hashcode 值生成数组下标（通过内存
地址直接查找，没有任何判断），时间复杂度完美情况下可以达到 n1（和数组相同，但是比数组用着爽多了，但是需要多出很多内存，相当于以空间换时间）。

3. String 类型的 hashcode 方法
在 JDK 中，Object 的 hashcode 方法是本地方法，也就是用 c 语言或 c++ 实现的，该方法直接返回对象的 内存地址。这么做会有说明问题呢？我们用代码看看：

class Test1{

  String name;

  public Test1(String name) {
    this.name = name;
  }

  public static void main(String[] args) {
    Map<Test1, String> map = new HashMap<>(4);
    map.put(new Test1("hello"), "hello");
    String hello = map.get(new Test1("hello"));
    System.out.println(hello);
  }
}

这段代码打印出来的会是什么呢？ 答： null。因为我们没有重写 hashCode 方法，所有，HashMap 内部使用的是该对象的内存地址，那么肯定不一样。我们第一个对
象根本就没有存，因此，返回就是 null。这里就可以看出来重写 hashCode 的重要性。

JDK 中，我们经常把 String 类型作为 key，那么 String 类型是如何重写 hashCode 方法的呢？

我们看看代码：

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

代码非常简单，就是使用 String 的 char 数组的数字每次乘以 31 再叠加最后返回，因此，每个不同的字符串，返回的 hashCode 肯定不一样。那么为什么使用 31 呢？

4. 为什么大部分 hashcode 方法使用 31
如果有使用 eclipse 的同学肯定知道，该工具默认生成的 hashCode 方法实现也和 String 类型差不多。都是使用的 31 ，那么有没有想过：为什么要使用 31 呢？

在名著 《Effective Java》第 42 页就有对 hashCode 为什么采用 31 做了说明：

根据素数的特性，与素数相乘得到的结果比其他方式更容易产生唯一性，也就是说产生 hash 值重复的概率比较小。
之所以使用 31， 是因为他是一个奇素数。如果乘数是偶数，并且乘法溢出的话，信息就会丢失，因为与2相乘等价于移位运算（低位补0）。使用素数的好处并不很明显，但是习惯
上使用素数来计算散列结果。 31 有个很好的性能，即用移位和减法来代替乘法，可以得到更好的性能： 31 * i == (i << 5） - i,
(证明：2*2*2*2*2=32，相当于左移5位，等于与32相乘)。 现代的 VM 可以自动完成这种优化。
这个公式可以很简单的推导出来。

这个问题在 SO 上也有讨论： https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier%EF%BC%89

可以看到，使用 31 最主要的还是为了性能。当然用 63 也可以。但是 63 的溢出风险就更大了。那么15 呢？仔细想想也可以。

在《Effective Java》也说道：编写这种散列函数是个研究课题，最好留给数学家和理论方面的计算机科学家来完成。我们此次最重要的是知道了为什么使用31。

5. HashMap 的 hash 算法的实现原理（为什么右移 16 位，为什么要使用 ^ 位异或）
好了，知道了 hashCode 的生成原理了，我们要看看今天的主角，hash 算法。

其实，这个也是数学的范畴，从我们的角度来讲，只要知道这是为了更好的均匀散列表的下标就好了，但是，就是耐不住好奇心啊！ 能多知道一点就是一点，我们来看看 HashMap 的 hash 算法（JDK 8）.

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

乍看一下就是简单的异或运算和右移运算，但是为什么要异或呢？为什么要移位呢？而且移位16？

在分析这个问题之前，我们需要先看看另一个事情，什么呢？就是 HashMap 如何根据 hash 值找到数组种的对象，我们看看 get 方法的代码：

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            // 我们需要关注下面这一行
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

我们看看代码中注释下方的一行代码：first = tab[(n - 1) & hash])。

使用数组长度减一 与运算 hash 值。这行代码就是为什么要让前面的 hash 方法移位并异或。

我们分析一下：

首先，假设有一种情况，对象 A 的 hashCode 为 1000010 00111000 10000011 11000000，对象 B 的 hashCode 为 0111011 10011100 01010000 10100000。

如果数组长度是16，也就是 15 与运算这两个数， 你会发现结果都是0。这样的散列结果太让人失望了。很明显不是一个好的散列算法。

但是如果我们将 hashCode 值右移 16 位，也就是取 int 类型的一半，刚好将该二进制数对半切开。并且使用位异或运算（如果两个数对应的位置相反，则结果为1，反之为0），
这样的话，就能避免我们上面的情况的发生。

总的来说，使用位移 16 位和 异或 就是防止这种极端情况。但是，该方法在一些极端情况下还是有问题，
比如：100 00000000 0000000 00000000 和 1 00000000 01000000 00000000 这两个数，如果数组长度是16，那么即使右移16位，在异或，hash 值还是会重复。但是
为了性能，对这种极端情况，JDK 的作者选择了性能。毕竟这是少数情况，为了这种情况去增加 hash 时间，性价比不高。

6. HashMap 为什么使用 & 与运算代替模运算？
好了，知道了 hash 算法的实现原理还有他的一些取舍，我们再看看刚刚说的那个根据hash计算下标的方法：

tab[(n - 1) & hash]；

其中 n 是数组的长度。其实该算法的结果和模运算的结果是相同的。但是，对于现代的处理器来说，除法和求余数（模运算）是最慢的动作。

上面情况下和模运算相同呢？

a % b == (b-1) & a ,当b是2的指数时，等式成立。

我们说 & 与运算的定义：与运算 第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0；

当 n 为 16 时， 与运算 101010100101001001101 时，也就是
1111 & 101010100101001001000 结果：1000 = 8
1111 & 101000101101001001001 结果：1001 = 9
1111 & 101010101101101001010 结果： 1010 = 10
1111 & 101100100111001101100 结果： 1100 = 12

可以看到，当 n 为 2 的幂次方的时候，减一之后就会得到 1111* 的数字，这个数字正好可以掩码。并且得到的结果取决于 hash 值。因为 hash 值是1，那么最终的结
果也是1 ，hash 值是0，最终的结果也是0。

7. HashMap 的容量为什么建议是 2的幂次方？
到这里，我们提了一个关键的问题： HashMap 的容量为什么建议是 2的幂次方？正好可以和上面的话题接上。楼主就是这么设计的。

为什么要 2 的幂次方呢？

我们说，hash 算法的目的是为了让hash值均匀的分布在桶中（数组），那么，如何做到呢？试想一下，如果不使用 2 的幂次方作为数组的长度会怎么样？

假设我们的数组长度是10，还是上面的公式：
1010 & 101010100101001001000 结果：1000 = 8
1010 & 101000101101001001001 结果：1000 = 8
1010 & 101010101101101001010 结果： 1010 = 10
1010 & 101100100111001101100 结果： 1000 = 8

看到结果我们惊呆了，这种散列结果，会导致这些不同的key值全部进入到相同的插槽中，形成链表，性能急剧下降。

所以说，我们一定要保证 & 中的二进制位全为 1，才能最大限度的利用 hash 值，并更好的散列，只有全是1 ，才能有更多的散列结果。如果是 1010，有的散列结果是永远都
不会出现的，比如 0111，0101，1111，1110…….，只要 & 之前的数有 0， 对应的 1 肯定就不会出现（因为只有都是1才会为1）。大大限制了散列的范围。

8. 我们自定义 HashMap 容量最好是多少？
那我们如何自定义呢？自从有了阿里的规约插件，每次楼主都要初始化容量，如果我们预计我们的散列表中有2个数据，那么我就初始化容量为2嘛？

绝对不行，如果大家看过源码就会发现，如果Map中已有数据的容量达到了初始容量的 75%，那么散列表就会扩容，而扩容将会重新将所有的数据重新散列，性能损失严重，所以，
我们可以必须要大于我们预计数据量的 1.34 倍，如果是2个数据的话，就需要初始化 2.68 个容量。当然这是开玩笑的，2.68 不可以，3 可不可以呢？肯定也是不可以的，
我前面说了，如果不是2的幂次方，散列结果将会大大下降。导致出现大量链表。那么我可以将初始化容量设置为4。 当然了，如果你预计大概会插入 12 条数据的话，那么初
始容量为16简直是完美，一点不浪费，而且也不会扩容。

总结
好了，分析完了 hashCode 和 hash 算法，让我们对 HashMap 又有了全新的认识。当然，HashMap 中还有很多有趣的东西值得挖掘，楼主会继续写下去。争取将 HashMap 
的衣服扒光。

总的来说，通过今天的分析，对我们今后使用 HashMap 有了更多的把握，也能够排查一些问题，比如链表数很多，肯定是数组初始化长度不对，如果某个map很大，注意，肯定是事
先没有定义好初始化长度，假设，某个Map存储了10000个数据，那么他会扩容到 20000，实际上，根本不用 20000，只需要 10000* 1.34= 13400 个，然后向上找到一个2 
的幂次方，也就是 16384 初始容量足够。

【hash算法】
我们以HashMap的hash算法来看，个人认为这是很值得搞懂的hash算法，设计超级超级巧妙
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

这是hashMap的hash算法，我们一步一步来看
(h = key.hashCode()) ^ (h >>> 16)

hashCode就hashCode嘛，为啥还要>>>16，这个 ^ 又是啥，不着急一个一个来说
hashMap我们知道默认初始容量是16，也就是有16个桶，那hashmap是通过什么来计算出put对象的时候该放到哪个桶呢
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

上面是hashmap的getNode方法，对hashmap源码有兴趣的同学自行研究，我们今天主要看这一句：(n - 1) & hash
也就是说hashmap是通过数组长度-1&key的hash值来计算出数组下标的，这里的hash值就是上面(h = key.hashCode()) ^ (h >>> 16)计算出来的值
不要慌不要慌不要慌，看不懂没关系，我们现在总结下目前的疑问
•为什么数组长度要 - 1，直接数组长度&key.hashCode不行吗
•为什么要length-1 & key.hashCode计算下标，而不是用key.hashCode % length
•为什么要^运算
•为什么要>>>16

先说结论
•数组长度-1、^运算、>>>16，这三个操作都是为了让key在hashmap的桶中尽可能分散
•用&而不用%是为了提高计算性能

我们先看下如果数组长度不-1和不进行>>>16运算造成的结果，知道了结果我们后面才来说为什么，这样子更好理解
log.info("数组长度不-1：{}", 16 & "郭德纲".hashCode());//0
log.info("数组长度不-1：{}", 16 & "彭于晏".hashCode());//0
log.info("数组长度不-1：{}", 16 & "李小龙".hashCode());//16
log.info("数组长度不-1：{}", 16 & "蔡徐鸡".hashCode());//16
log.info("数组长度不-1：{}", 16 & "唱跳rap篮球鸡叫".hashCode());//16

log.info("数组长度-1但是不进行异或和>>>16运算：{}", 15 & "郭德纲".hashCode());//8
log.info("数组长度-1但是不进行异或和>>>16运算：{}", 15 & "彭于晏".hashCode());//14
log.info("数组长度-1但是不进行异或和>>>16运算：{}", 15 & "李小龙".hashCode());//8
log.info("数组长度-1但是不进行异或和>>>16运算：{}", 15 & "蔡徐鸡".hashCode());//2
log.info("数组长度-1但是不进行异或和>>>16运算：{}", 15 & "唱跳rap篮球鸡叫".hashCode());//14

log.info("数组长度-1并且进行异或和>>>16运算：{}", 15 & ("郭德纲".hashCode()^("郭德纲".hashCode()>>>16)));//4
log.info("数组长度-1并且进行异或和>>>16运算：{}", 15 & ("彭于晏".hashCode()^("彭于晏".hashCode()>>>16)));//14
log.info("数组长度-1并且进行异或和>>>16运算：{}", 15 & ("李小龙".hashCode()^("李小龙".hashCode()>>>16)));//7
log.info("数组长度-1并且进行异或和>>>16运算：{}", 15 & ("蔡徐鸡".hashCode()^("蔡徐鸡".hashCode()>>>16)));//13
log.info("数组长度-1并且进行异或和>>>16运算：{}", 15 & ("唱跳rap篮球鸡叫".hashCode()^("唱跳rap篮球鸡叫".hashCode()>>>16)));//2

//运行结果
数组长度不-1：0
数组长度不-1：0
数组长度不-1：16
数组长度不-1：16
数组长度不-1：16
数组长度-1但是不进行异或和>>>16运算：8
数组长度-1但是不进行异或和>>>16运算：14
数组长度-1但是不进行异或和>>>16运算：8
数组长度-1但是不进行异或和>>>16运算：2
数组长度-1但是不进行异或和>>>16运算：14
数组长度-1并且进行异或和>>>16运算：4
数组长度-1并且进行异或和>>>16运算：14
数组长度-1并且进行异或和>>>16运算：7
数组长度-1并且进行异或和>>>16运算：13
数组长度-1并且进行异或和>>>16运算：2

一下就看出区别了哇，第一组返回的下标就只有0和16，第二组也只有2、8、14，第三组的下标4、14、7、13、2就很分散，这才是我们想要的
这结合hashMap来看，前两组造成的影响就是key几乎全部怼到同一个桶里，及其不分散，用行话讲就是有太多的hash冲突，这对hashMap的性能有很大影响，hash冲突造成的链表红黑
树转换那些具体的原因这里就不展开说了
原理
知道了结果，现在说说其中的玄学

1、为什么数组长度要 - 1，直接数组长度&key.hashCode不行吗
hashMap默认长度是16，看看16的二进制码是多少
log.info("16的二进制码：{}",Integer.toBinaryString(16));  
//16的二进制码：10000，

再看看key.hashCode()的二进制码是多少，以郭德纲为例
log.info("key的二进制码：{}",Integer.toBinaryString("郭德纲".hashCode()));
//key的二进制码：10001011000001111110001000

length & key.hashCode()  => 10000 & 10001011000001111110001000
位数不够，高位补0，即

0000 0000 0000 0000 0000 0001 0000 
                & 
0010 0010 1100 0001 1111 1000 1000

&运算规则是第一个操作数的的第n位于第二个操作数的第n位都为1才为1，否则为0
所以结果为0000 0000 0000 0000 0000 0000 0000，即 0

冷静分析一波，问题就出在16的二进制码上，它码是10000，只有遇到hash值二进制码倒数第五位为1的key他们&运算的结果才不等于0，这句话好好理解下，看不懂就别强制看，去摸会儿鱼再回来看
再来看16-1的二进制码，它码是1111，同样用郭德纲这个key来举例
(length-1) & key.hashCode()  => 1111 & 10001011000001111110001000
位数不够，高位补0，即

0000 0000 0000 0000 0000 0000 1111 
                & 
0010 0010 1100 0001 1111 1000 1000

&运算规则是第一个操作数的的第n位于第二个操作数的第n位都为1才为1，否则为0
所以结果为0000 0000 0000 0000 0000 0000 1000，即 8

如果还看不出这其中的玄机，你就多搞几个key来试试，总之记住，限制它们&运算的结果就会有很多种可能性了，不再受到hash值二进制码倒数第五位为1才能为1的限制

2、为什么要length-1&key.hashCode计算下标，而不是用key.hashCode%length
这个其实衍生出三个知识点
1、其实(length-1)&key.hashCode计算出来的值和key.hashCode%length是一样的
log.info("(length-1)&key.hashCode：{}",15&"郭德纲".hashCode());
log.info("key.hashCode%length：{}","郭德纲".hashCode()%16);

//  (length-1)&key.hashCode：8
//  key.hashCode%length：8

那你可能更蒙逼了，都一样的为啥不用%，这就要说到第二个知识点
2、只有当length为2的n次方时，(length-1)&key.hashCode才等于key.hashCode%length，比如当length为15时
log.info("(length-1)&key的hash值：{}",14&"郭德纲".hashCode());
log.info("key的hash值%length：{}","郭德纲".hashCode()%15);

//  (length-1)&key.hashCode：8
//  key.hashCode%length：3

可能又有小朋友会思考，我不管那我就想用%运算，要用魔法打败魔法，请看第三点

3、用&而不用%是为了提高计算性能，对于处理器来讲，&运算的效率是高于%运算的，就这么简单，除此之外，除法的效率也没&高

4、为什么要进行^运算
这是异或运算符，第一个操作数的的第n位于第二个操作数的第n位相反才为1，否则为0
我们多算几个key的值出来对比
//不进行异或运算返回的数组下标
log.info("郭德纲：{}", Integer.toBinaryString("郭德纲".hashCode()));            
log.info("彭于晏：{}", Integer.toBinaryString("彭于晏".hashCode()));            
log.info("李小龙：{}", Integer.toBinaryString("李小龙".hashCode()));            
log.info("蔡徐鸡：{}", Integer.toBinaryString("蔡徐鸡".hashCode()));            
log.info("唱跳rap篮球鸡叫：{}", Integer.toBinaryString("唱跳rap篮球鸡叫".hashCode()));

00001000101100000111111000 1000
00000101110000001000011010 1110
00000110001111100100010011 1000
00000111111111111100010111 0010
10111010111100100011001111 1110

进行&运算，看下它们返回的数组下标，length为16的话，只看后四位即可
8
14
8
2
14

//进行异或运算返回的数组下标
log.info("郭德纲：{}", Integer.toBinaryString("郭德纲".hashCode()^("郭德纲".hashCode()>>>16)));                  
log.info("彭于晏：{}", Integer.toBinaryString("彭于晏".hashCode()^("彭于晏".hashCode()>>>16)));                  
log.info("李小龙：{}", Integer.toBinaryString("李小龙".hashCode()^("李小龙".hashCode()>>>16)));                  
log.info("蔡徐鸡：{}", Integer.toBinaryString("蔡徐鸡".hashCode()^("蔡徐鸡".hashCode()>>>16)));                  
log.info("唱跳rap篮球鸡叫：{}", Integer.toBinaryString("唱跳rap篮球鸡叫".hashCode()^("唱跳rap篮球鸡叫".hashCode()>>>16)));

0000001000101100000111011010 0100
0000000101110000001000001101 1110
0000000110001111100100001011 0111
0000000111111111111100001000 1101
0010111010111100101000100100 0010

进行&运算，看下它们返回的数组下标，length为16的话，只看后四位即可
4
14
7
13
2

很明显，做了^运算的数组下标更分散
5、为什么要>>>16
这是无符号右移16位，位数不够，高位补0
其实>>>16和^运算是相辅相成的关系，目的都是为了让数组下标更分散，看一看>>>16的效果就知道了
（单独看<<<16可能看不出啥效果，但搭配上^就很容易看出来了，总之，记住这是为了让数组下标更加分散的骚操作）
log.info("郭德纲：{}", Integer.toBinaryString("郭德纲".hashCode()));  
log.info("郭德纲>>>16：{}", Integer.toBinaryString("郭德纲".hashCode()>>>16)); 
0000 0010 0010 1100 0001 1111 1000 1000
0000 0000 0000 0000 0000 0010 0010 1100

log.info("彭于晏：{}", Integer.toBinaryString("彭于晏".hashCode()));  
log.info("彭于晏>>>16：{}", Integer.toBinaryString("彭于晏".hashCode()>>>16)); 
0000 0001 0111 0000 0010 0001 1010 1110
0000 0000 0000 0000 0000 0001 0111 0000

log.info("李小龙：{}", Integer.toBinaryString("李小龙".hashCode()));    
log.info("李小龙>>>16：{}", Integer.toBinaryString("李小龙".hashCode()>>>16)); 
0000 0001 1000 1111 1001 0001 0011 1000
0000 0000 0000 0000 0000 0001 1000 1111

log.info("蔡徐鸡：{}", Integer.toBinaryString("蔡徐鸡".hashCode()));  
log.info("蔡徐鸡>>>16：{}", Integer.toBinaryString("蔡徐鸡".hashCode()>>>16));
0000 0001 1111 1111 1111 0001 0111 0010
0000 0000 0000 0000 0000 0001 1111 1111

log.info("唱跳rap篮球鸡叫：{}", Integer.toBinaryString("唱跳rap篮球鸡叫".hashCode()));          
log.info("唱跳rap篮球鸡叫>>>16：{}", Integer.toBinaryString("唱跳rap篮球鸡叫".hashCode()>>>16));                                                                           
0010 1110 1011 1100 1000 1100 1111 1110
0000 0000 0000 0000 0010 1110 1011 1100

 */
public class hash与hashcode {
	
   public static void main(String[] args) {
       Student s1 = new Student(18, "张三");
       Map<Student, Integer> scores = new HashMap<>();
       scores.put(s1, 98);
       System.out.println(scores.get(new Student(18, "张三")));

       ArrayList<Integer> ints = new ArrayList<Integer>();
       ArrayList<String> strs = new ArrayList<String>();
       ArrayList list;
       list = ints;
       list = strs;
    
       
   }
}
class Student {
   private int age;
   private String name;

    public Student(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        Student student = (Student) o;
        return age == student.age &&
                Objects.equals(name, student.name);
    }
}

